⟸ Go Back ⟸

Exercise 5 (Homework 7).

(P, NP, Kleene star)

Closure under the Kleene star

1. Show that \mathsf{P} is closed under the Kleene star.

   Tip

   Use dynamic programming. Given a set A \in \mathsf{P} over \Sigma and an input x = x_1 \dots x_n for x_i \in \Sigma, build a table indicating for each i < j whether the substring x_i \dots x_j is in A^*.

2. Show that \mathsf{NP} is closed under the Kleene star.